package Solution;


import java.util.*;

public class Solution {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public int rob(TreeNode root) {
        // dp[i][0] 表示偷这家的最大值
        // dp[i][1] 表示不偷这家的最大值
        // 如果偷 那就不能偷左孩子和右孩子
        // 如果不偷，那左孩子和右孩子偷不偷都可以
        int[] ans = dfs(root);
        return Math.max(ans[0],ans[1]);
    }
    private int[] dfs(TreeNode root) {
        if(root == null) return new int[]{0,0};
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        int[] ans = new int[2];
        // 偷
        ans[0] = left[1] + right[1] + root.val;
        // 不偷
        ans[1] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);

        return ans;
    }
    public int coinChange(int[] coins, int amount) {
        // 每种硬币的数量是无限的
        // dp[i] 表示凑成金额i需要的最少硬币数
        // dp[i] = min(dp[i-coins[j]])+1 dp[i] == -1 表示不能凑成
        // 如果不存在的话
        int[] dp = new int[amount+1];
        for (int i = 1; i <= amount; i++) {
            int min = -1;
            for (int x: coins) {
                if(i-x>=0) {
                    if(dp[i-x] != -1) {
                        if(min == -1) min = dp[i-x];
                        else min = Math.min(min,dp[i-x]);
                    }
                }
                dp[i] = min;
            }
        }
        return dp[amount];
    }
    public int integerBreak(int n) {
        // 拆分成k个整数的和乘积最大
        // 暴力搜索
//        return dfs(n,new int[n+1]);
        // dp[i] 表示 i拆分的最大乘积
        // dp[i] Math.max(dp[j],j*j-1);
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                int max = Math.max(dp[j]*(i-j),j*(i-j));
                dp[i] = Math.max(max,dp[i]);
            }
        }
        return dp[n];
    }
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 10;
        }
        int res = 10, cur = 9;
        for (int i = 0; i < n - 1; i++) {
            cur *= 9 - i;
            res += cur;
        }
        return res;
    }
    public List<Integer> largestDivisibleSubset(int[] nums) {
        // 最大整除子集
//        List<Integer> ans = new ArrayList<>();
//        trackBack(ans,new Stack<>(),nums,0);
//        return ans;
        // 先排序
        // dp[i] 表示以第i个元素结尾的最大的整除子集
        // dp[i] = dp[j-1]+1 // nums[j]是j<i&&最右边的能被nums[i]整除的
        Arrays.sort(nums);
        int n = nums.length;
        List<Integer>[] dp = new List[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new ArrayList<>();
        }
        dp[0].add(nums[0]);
        for (int i = 1; i < n; i++) {
            int j = i-1;
            while (j>=0) {
                if(nums[i]%nums[j] == 0) {
                    if(dp[i].size() < dp[j].size()) {
                        dp[i].clear();
                        dp[i].addAll(dp[j]);
                    }
                }
                j--;
            }
            dp[i].add(nums[i]);
        }
        return Arrays.stream(dp).max(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return o1.size()-o2.size();
            }
        }).get();
    }
    private void trackBack(List<Integer> ans, Stack<Integer> path, int[] nums, int startIndex) {
        if(path.size() > ans.size()) {
            ans.clear();
            for (int val: path) {
                ans.add(val);
            }
        }
        for (int i = startIndex; i < nums.length; i++) {
            boolean bol = true;
            for (int val: path) {
                if(nums[i]%val!=0 && val%nums[i] != 0) {
                    bol = false;
                    break;
                }
            }
            if(bol) {
                path.push(nums[i]);
                trackBack(ans,path,nums,i+1);
                path.pop();
            }
        }
    }
    public int getMoneyAmount(int n) {
        // dp[i][j] 表示在 [i,j]范围内的最小保证
        // dp[i][j] = max(dp[i][mid-1],dp[mid+1][j])
        // 1--n
        // 保证不会输的最小金额
        // n == 1 0  // 坑定不会猜错
        // n == 2 猜1 对了就是0 错了就是 1
        // n == 3 猜2 对了0 错了就是2
        int[][] f = new int[n + 1][n + 1];
        for (int i = n - 1; i >= 1; i--) {
            for (int j = i + 1; j <= n; j++) {
                f[i][j] = j + f[i][j - 1];
                for (int k = i; k < j; k++) {
                    f[i][j] = Math.min(f[i][j], k + Math.max(f[i][k - 1], f[k + 1][j]));
                }
            }
        }
        return f[1][n];
    }
    public int wiggleMaxLength(int[] nums) {
        // 摆动序列
        // dp[i][0] 表示以nums[i] 结尾的并且nums[i]是山谷
        // dp[i][1] 表示以nums[i] 结尾的并且nums[i]是山峰
        int n = nums.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 1;
        dp[0][1] = 1;
        int ans = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    dp[i][0] = Math.max(dp[i][0],dp[j][1]+1);
                }
                if(nums[j] > nums[i]) {
                    dp[i][1] = Math.max(dp[i][1],dp[j][0]+1);
                }
            }
            ans = Math.max(ans,dp[i][0]);
            ans = Math.max(ans,dp[i][1]);
        }
        return ans;// 1 2 3 4 5 6 7 8
    }
    public int combinationSum4(int[] nums, int target) {
        // dp[i][j] 表示前i个元素中总和为j的组合方法
        // 每个元素可以选k个 (nums[i]*k<=target)
//        int n = nums.length;
//        int[][] dp = new int[n][target+1];
//        for (int i = 0; i < n; i++) {
//            dp[i][0] = 1;
//        }
//        for (int i = 0; i <= target; i++) {
//            if(i%nums[0] == 0) dp[0][i] = 1;
//        }
//        for (int i = 1; i < n; i++) {
//            for (int j = 1; j < target; j++) {
//                for (int k = 0; k*nums[i] <= j; k++) {
//                    dp[i][j] += dp[i-1][j-k*nums[i]];
//                }
//            }
//        }
//        return dp[n-1][target];
        // dp[i] 表示和为i的方案数目
        int n = nums.length;
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int x: nums) {
                dp[i] += dp[i-x];
            }
        }
        return dp[target];
    }
    public int maxRotateFunction(int[] nums) {
        // 4 3 2 6
        // 0*4 + 1*3 +2*2 +3*6
        // 0*6 + 1*4 +2*3 + 3*2
        // 每次移动 就相当于 + (sum-last*(n-1))
        int sum = Arrays.stream(nums).sum();
        int n = nums.length;
        int[] dp = new int[n+1];
        for (int i = 0; i < n; i++) {
            dp[0] += nums[i]*i;
        }
        int ans = dp[0];
        int last = n-1;
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i-1] + (sum-nums[last]*(n));
            last--;
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
    public int integerReplacement(int n) {
        return dfs(n);
    }
    private int dfs(int n) {
        if(n == 1) return 0;
        if(n%2 == 0) return dfs(n/2)+1;
        return Math.min(dfs((n)/2),dfs(n/2+1))+2;
    }
    public int numberOfArithmeticSlices(int[] nums) {
        // 暴力杯
        // 枚举连续序列 nums[i,j]
//        int ans = 0;
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i+2; j < nums.length; j++) {
//                int d = nums[i+1] - nums[i];
//                boolean bol = true;
//                for (int k = i; k+1 <= j; k++) {
//                    if(nums[k+1] - nums[k] != d) {
//                        bol = false;
//                        break;
//                    }
//                }
//                if(bol) {
//                    ans++;
//                }
//            }
//        }
//        return ans;
//        // dp[i] 表示以nums[i] 结尾的等差数列的最大长度
//        // 如果 nums[i]-nums[i-1] == nums[i-1]-nums[i-2] dp[i] = dp[i-1] + 1;
//        // 否则 dp[i] = 2;
//        int n = nums.length;
//        int[] dp = new int[n];
//        dp[0] = 1;
//        dp[1] = 2;
//        for (int i = 2; i < n; i++) {
//            if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
//                dp[i] = dp[i-1] +1 ;
//            } else {
//                dp[i] = 2;
//            }
//        }
//        return dp[n-1];
        int n = nums.length;
        if(n == 1) {
            return 0;
        }
        int d = nums[0] - nums[1],t = 0;
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if(nums[i-1] == nums[i] - d) {
                t++;
            } else {
                d = nums[i-1] - nums[i];
                t = 0;
            }
            ans += t;
        }
        return ans;
    }
    public boolean canPartition(int[] nums) {
        // 分割等和子集
        // dp[i][j]前i个元素能不能凑成和为j的子集
        // dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
        int total = Arrays.stream(nums).sum();
        if((total&1) == 1) return false;
        int n = nums.length;
        boolean [][] dp = new boolean[n][total/2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(i == 0) {
                    dp[i][j] = nums[i] == j;
                } else {
                    dp[i][j] = dp[i-1][j];
                    if(j-nums[i] >= 0) dp[i][j] |= dp[i-1][j-nums[i]];
                }
            }
        }
        return dp[n-1][total>>1];
    }
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length == 0) return 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int n = intervals.length;
        int[] f = new int[n];
        Arrays.fill(f,1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(intervals[j][1] <= intervals[i][0]) {
                    f[i] = Math.max(f[i],f[j]+1);
                }
            }
        }
        return n - Arrays.stream(f).max().getAsInt();
    }
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        Stack<int[]> stack = new Stack<>();
        stack.push(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if(stack.peek()[1] < intervals[i][0]) {
                stack.push(intervals[i]);
            } else {
                stack.peek()[1] = Math.max(stack.peek()[1],intervals[i][1]);
            }
        }
        return stack.toArray(new int[stack.size()][]);
    }
    public int findSubstringInWraproundString(String p) {
        int[] dp = new int[26];
        int k = 0;
        for (int i = 0; i < p.length(); ++i) {
            if (i > 0 && (p.charAt(i) - p.charAt(i - 1) + 26) % 26 == 1) { // 字符之差为 1 或 -25
                ++k;
            } else {
                k = 1;
            }
            dp[p.charAt(i) - 'a'] = Math.max(dp[p.charAt(i) - 'a'], k);
        }
        return Arrays.stream(dp).sum();
    }
    //    public boolean makesquare(int[] matchsticks) {
//        // 暴力搜索
//        // 对于第i根火柴 可以放的位置有四个
//        // 只要其中有一个满足条件 则返回true
////        return dfs(0,matchsticks,0,0,0,0);
//        // dp[i]
//        int totalSum = Arrays.stream(matchsticks).sum();
//        if(totalSum %4 != 0) return false;
//        Arrays.sort(matchsticks);
//        return dfs(matchsticks.length-1,matchsticks,0,0,0,0,totalSum/4);
//    }
    private boolean dfs(int index,int[] matchistcks,int up,int down,int left,int right,int totalSum) {
        if(index == -1) {
            if(up == down && left == right && up == left) {
                return true;
            }
            return false;
        }
        if(up > totalSum || down > totalSum || left > totalSum || right > totalSum) return false;
        boolean ans = false;
        ans = dfs(index-1,matchistcks,up+matchistcks[index],down,left,right,totalSum)||
                dfs(index-1,matchistcks,up,down+matchistcks[index],left,right,totalSum)||
                dfs(index-1,matchistcks,up,down,left+matchistcks[index],right,totalSum)||
                dfs(index-1,matchistcks,up,down,left,right+matchistcks[index],totalSum);
        return ans;
    }
    public boolean makesquare(int[] matchsticks) {
        int totalLen = Arrays.stream(matchsticks).sum();
        if (totalLen % 4 != 0) {
            return false;
        }
        int len = totalLen / 4, n = matchsticks.length;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int s = 1; s < (1 << n); s++) {
            for (int k = 0; k < n; k++) {
                if ((s & (1 << k)) == 0) {
                    continue; // 已经放了
                }
                int s1 = s & ~(1 << k);
                if (dp[s1] >= 0 && dp[s1] + matchsticks[k] <= len) {
                    dp[s] = (dp[s1] + matchsticks[k]) % len;
                    break;
                }
            }
        }
        return dp[(1 << n) - 1] == 0;
    }
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len][m+1][n+1];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    int zero = 0,one = 0;
                    String s = strs[i];
                    for (char c: s.toCharArray()) {
                        if(c == '0') zero++;
                        else one++;
                    }
                    if(i!=0) {
                        if(j-zero < 0 || k-one < 0) {
                            dp[i][j][k] = dp[i-1][j][k];
                        } else {
                            dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-zero][k-one]+1);
                        }
                    } else {
                        dp[i][j][k] =  (zero<=j && one<=k) ? 1: 0;
                    }
                }
            }
        }
        return dp[len-1][m][n];
    }
    public int findTargetSumWays(int[] nums, int target) {
//        return dfs(nums,target,0,0);
        // neg = (sum-target)/2
        // 问题就转换成 从数组中选元素，使其和为neg的方法有多少
        // dp[i][j] 表示前i个元素中，和为j的方案数目
        // dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = nums.length, neg = diff / 2;
        int[][] dp = new int[n][neg+1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= neg; j++) {
                if(i>0) {
                    dp[i][j] += dp[i-1][j];
                    if(j-nums[i] >= 0) {
                        dp[i][j] += dp[i-1][j-nums[i]];
                    }
                } else {
                    if(j == 0) dp[i][j] = 1; // 不选
                    if(j == nums[i]) dp[i][j]++;
                }
            }
        }
        return dp[n-1][neg];
    }
    public int longestPalindromeSubseq(String s) {
        // dp[i][j] 表示s[i,j] 之间的最长回文串长度

        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n-1; i >=0 ; i--) {
            for (int j = i; j <n ; j++) {
                if(j == i) {
                    dp[i][j] = 1;
                } else if (j == i+1) {
                    dp[i][j] = s.charAt(i) == s.charAt(j)? 2: 1;
                } else {
                    if(s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = dp[i+1][j-1]+2;
                    } else {
                        dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                    }
                }
            }
        }
        return dp[0][n-1];
    }
    public int change(int amount, int[] coins) {
        // 凑成amount的组合
        // 完全背包
        // dp[i][j] 表示前i个元素中凑成j的组合方案
        // dp[i][j] = dp[i-1][j] + dp[i-1][j-x] + dp[i-1][j-x*2] + dp[i-1][j-x*3] ...
//        int n = coins.length;
//        int[][] dp = new int[n][amount+1];
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j <= amount; j++) {
//                int x = coins[i];
//                if(i > 0) {
//                    for (int k = 0; k*x <= j; k++) {
//                        if(k*x == j) dp[i][j] ++;
//                        else dp[i][j] += dp[i-1][j-k*x];
//                    }
//                } else {
//                    // 如果只有一个元素的情况下
//                    if(j == 0) dp[i][j] = 1;
//                    else if (j%x == 0) dp[i][j] = 1;
//                }
//            }
//        }
//        return dp[n-1][amount];
        // dp[i]表示和为i有多少种组合
        // dp[i] = dp[i-coins[i]]
        int n = coins.length;
        int[] dp = new int[amount+1];
        dp[0] = 1; // 一个都不选
        for (int coin: coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i-coin];
            }
        }
        return dp[amount];
    }
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
            return false;
        }
        return dfs(0,0,new HashMap<>(),maxChoosableInteger,desiredTotal);
    }
    private boolean dfs(int used, int curSum, Map<Integer,Boolean> map, int maxChosableInteger, int desiredTotal) {
        if(!map.containsKey(used)) {
            boolean ans = false;
            for (int i = 0; i < maxChosableInteger; i++) {
                int state = (used >> i) & 1;
                if(state == 0) {
                    if(curSum+i+1 >= desiredTotal) {
                        ans = true;
                        break;
                    }
                    if(!dfs(used|(1<<i),curSum+i+1,map,maxChosableInteger,desiredTotal)) {
                        ans = true;
                        break;
                    }
                }
            }
            map.put(used,ans);
        }
        return map.get(used);
    }
    public int countArrangement(int n) {
//        int[] ans = new int[1];
//        trackBack(new HashSet<>(),n,ans,1);
//        return ans[0];
        // 状态压缩 + 动态规划
        int[] f = new int[1 << n];
        f[0] = 1;
        for (int mask = 1; mask < (1 << n); mask++) {
            int num = Integer.bitCount(mask);
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0 && ((num % (i + 1)) == 0 || (i + 1) % num == 0)) {
                    f[mask] += f[mask ^ (1 << i)];
                }
            }
        }
        return f[(1 << n) - 1];
    }
    private void trackBack(Set<Integer> used,int n,int [] ans,int index) {
        if(used.size() == n) {
            ans[0]++;
            return;
        }
        for (int i = 1; i <= n; i++) {
            if(!used.contains(i)) {
                if(i%index == 0 || index%i == 0) {
                    used.add(i);
                    trackBack(used,n,ans,index+1);
                    used.remove(i);
                }
            }
        }
    }
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int[][] updateMatrix(int[][] matrix) {
        // 广度优先搜索
        int m = matrix.length, n = matrix[0].length;
        int[][] dist = new int[m][n];
        boolean[][] seen = new boolean[m][n];
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] == 0) {
                    queue.offer(new int[]{i,j});
                    seen[i][j] = true;
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int i = cell[0],j = cell[1];
            for (int d = 0; d < 4; d++) {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
                    dist[ni][nj] = dist[i][j] + 1;
                    queue.offer(new int[]{ni, nj});
                    seen[ni][nj] = true;
                }
            }
        }
        return dist;
    }
    class Node {
        double maxVal;
        double minVal;
        String minStr;
        String maxStr;

        public Node(double maxVal, double minVal) {
            this.maxVal = maxVal;
            this.minVal = minVal;
        }

        public Node() {
        }
    }
    public String optimalDivision(int[] nums) {
        int n = nums.length;
        Node[][] dp = new Node[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                dp[i][j] = new Node();
            }
        }
        for (int i = 0; i < n; i++) {
            dp[i][i].minVal = nums[i];
            dp[i][i].maxVal = nums[i];
            dp[i][i].minStr = String.valueOf(nums[i]);
            dp[i][i].maxStr = String.valueOf(nums[i]);
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j + i < n; j++) {
                for (int k = j; k < j + i; k++) {
                    if (dp[j][j + i].maxVal < dp[j][k].maxVal / dp[k + 1][j + i].minVal) {
                        dp[j][j + i].maxVal = dp[j][k].maxVal / dp[k + 1][j + i].minVal;
                        if (k + 1 == j + i) {
                            dp[j][j + i].maxStr = dp[j][k].maxStr + "/" + dp[k + 1][j + i].minStr;
                        } else {
                            dp[j][j + i].maxStr = dp[j][k].maxStr + "/(" + dp[k + 1][j + i].minStr + ")";
                        }
                    }
                    if (dp[j][j + i].minVal > dp[j][k].minVal / dp[k + 1][j + i].maxVal) {
                        dp[j][j + i].minVal = dp[j][k].minVal / dp[k + 1][j + i].maxVal;
                        if (k + 1 == j + i) {
                            dp[j][j + i].minStr = dp[j][k].minStr + "/" + dp[k + 1][j + i].maxStr;
                        } else {
                            dp[j][j + i].minStr = dp[j][k].minStr + "/(" + dp[k + 1][j + i].maxStr + ")";
                        }
                    }
                }
            }
        }
        return dp[0][n - 1].maxStr;
    }
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        final int MOD = 1000000007;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int outCounts = 0;
        int[][][] dp = new int[maxMove + 1][m][n];
        dp[0][startRow][startColumn] = 1;
        for (int i = 0; i < maxMove; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    int count = dp[i][j][k];
                    if (count > 0) {
                        for (int[] direction : directions) {
                            int j1 = j + direction[0], k1 = k + direction[1];
                            if (j1 >= 0 && j1 < m && k1 >= 0 && k1 < n) {
                                dp[i + 1][j1][k1] = (dp[i + 1][j1][k1] + count) % MOD;
                            } else {
                                outCounts = (outCounts + count) % MOD;
                            }
                        }
                    }
                }
            }
        }
        return outCounts;
    }
    public int minDistance(String word1, String word2) {
        // dp[i][j] 表示 word1的前i个字符变成word2的前j个字符的最少操作次数
        // 可以删除 word1[i] 或者 删除 word2[j]
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+1;
                }
            }
        }
        return dp[m][n];
    }
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
//        int n = nums.length;
//        int[][] dp = new int[n][2];
//        dp[0][0] = 0;
//        dp[0][1] = 0;
//        for (int i = 1; i < indexDifference; i++) {
//            int maxIndex = dp[i-1][0];
//            int minIndex = dp[i-1][1];
//
//            if(nums[maxIndex] >= nums[i]) {
//                dp[i][0] = maxIndex;
//            } else {
//                dp[i][1] = i;
//            }
//            if(nums[minIndex] <= nums[i]) {
//                dp[i][1] = minIndex;
//            } else {
//                dp[i][1] = i;
//            }
//        }
//        for (int i = indexDifference; i < n; i++) {
//            int max = dp[i-indexDifference][0];
//            int min = dp[i-indexDifference][1];
//
//            if(max - nums[i] >= valueDifference) {
//                // 最小元素的索引
//
//            }
//            if(nums[i] - min >= valueDifference) {
//
//            }
//
//            dp[i][0] = Math.max(nums[i],max);
//            dp[i][1] = Math.min(nums[i],min);
//        }
//        int n = nums.length;
//        // max是前i-indexDiff个元素的最大值索引
//        // min是前i-valDiff 个元素的最小值所哟因
//        int max = 0,min = 0;
//        for (int i = 1; i < indexDifference; i++) {
//            if(nums[max] < nums[i]) {
//                max = i;
//            }
//            if(nums[min] > nums[i]) {
//                min = i;
//            }
//        }
//        System.out.println(max +" "+min);
//        for (int i = indexDifference; i < n; i++) {
//            // 先检测
//            if(nums[i] - nums[min] >= valueDifference) {
//                return new int[]{min,i};
//            }
//            if(nums[max] - nums[i] >= valueDifference) {
//                return new int[]{max,i};
//            }
//
//            if(nums[i-indexDifference] > nums[max]) {
//                max = i-indexDifference;
//            }
//            if(nums[i-indexDifference] < nums[min]) {
//                min = i-indexDifference;
//            }
//        }
//        return new int[]{-1,-1};
        int n = nums.length;
        int maxIndex = 0;
        int minIndex = 0;
        for (int i = indexDifference; i < n; i++) {
            if(nums[i] - nums[minIndex] >= valueDifference) {
                return new int[]{i,minIndex};
            }
            if(nums[maxIndex] - nums[i] >= valueDifference) {
                return new int[]{i,maxIndex};
            }

            if(nums[i-indexDifference] > nums[maxIndex]) {
                maxIndex = i-indexDifference;
            }
            if(nums[i-indexDifference] < nums[minIndex]) {
                minIndex = i-indexDifference;
            }
        }
        return new int[]{-1,-1};
    }
    public String shortestBeautifulSubstring(String s, int k) {
        // 最短美丽子字符串
        String ans = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if(check(s.substring(i,j+1),k)) {
                    if(ans.equals("")) {
                        ans = s.substring(i,j+1);
                    } else {
                        String tmp = s.substring(i,j+1);
                        if(tmp.length() < ans.length()) {
                            ans = tmp;
                        } else if (tmp.length() == ans.length()) {
                            // 字典序
                            boolean check = false;
                            for (int l = 0; l < tmp.length(); l++) {
                                if(tmp.charAt(l) > ans.charAt(l)) {
                                    check = true;
                                    break;
                                } else if (tmp.charAt(l) < ans.charAt(l)) {
                                    check = false;
                                    break;
                                }
                            }
                            if(!check) {
                                ans = tmp;
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
    private boolean check(String s,int k) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '1') count++;
        }
        return count == k;
    }

//    private int dfs(int[] nums,int target,int curSum,int startIndex) {
//        if(startIndex == nums.length) {
//            if(curSum == target) return 1; // 可取
//            else return 0; // 不可取
//        }
//        return dfs(nums,target,curSum+nums[startIndex],startIndex+1)+
//                dfs(nums,target,curSum-nums[startIndex],startIndex+1);
//    }
//    public boolean predictTheWinner(int[] nums) {
//        // 预测玩家
//        // 深度搜索
//        for (int i = 0; i < nums.length; i++) {
//            nums[i]++;
//        }
//        return canWin(nums,0,nums.length-1,0,0);
//    }
//    private boolean canWin(int[] nums,int l,int r,int a,int b) {
//        // 判断当前玩家能不能赢
//        // 这种情况下能不能赢
//        if(l > r) {
//            return a >= b;
//        }
//        return !canWin(nums,l+1,r,b,a+nums[l])||
//                !canWin(nums,l,r-1,b,a+nums[r]);
//    }

    // 2 3  4  0.5 0.6 7 8 9    3*4*0.5 = 6
    // 2 6 24  12  7.2
//    private int dfs(int n,int[] memo) {
//        if(memo[n] != 0) return memo[n];
//        if(n == 1) return 1;
//        int ans = 0;// 乘积最大
//        for (int i = 1; i <= n-1; i++) {
//            ans = Math.max(ans,i*dfs(n-i,memo));
//            ans = Math.max(ans,i*(n-i));
//        }
//        memo[n] = ans;
//        return ans;
//    }
}
